6.8 KB · ⇊ 2 parts · ⤓ Micron 6.8 KB · ⤓ HTML 22.0 KB

top

Nella mwawteoria della complessità computazionale, la mwbaclasse di complessità mwbqNEXPTIME (a volte detta mwbgNEXP) è l'insieme dei mwbwproblemi decisionali risolvibili da una mwcamacchina di Turing non deterministica in tempo mwcq O ( 2 p ( n ) ) {\displaystyle O(2^{p(n)})} , dove mwcg p ( n ) {\displaystyle p(n)} è una funzione polinomiale.

In termini di NTIME, mwda N E X P T I M E = ⋃ ⋃ k ∈ ∈ N N T I M E ( 2 n k ) {\textstyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})} .

Sappiamo che mwdg P ⊆ ⊆ N P ⊆ ⊆ E X P T I M E ⊆ ⊆ N E X P T I M E {\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {EXPTIME}}\subseteq {\mathsf {NEXPTIME}}} e, per il teorema della gerarchia temporale, che mwdw N P ⊊ ⊊ N E X P T I M E {\displaystyle {\mathsf {NP}}\subsetneq {\mathsf {NEXPTIME}}} .

Se mweqP = NP, allora NEXPTIME = EXPTIME (ragionamento di padding); più precisamente, E ≠ NE se e solo se esistono linguaggi sparsi in mwegNP che non sono in mwewP.

• NEXPTIME-completo

• Esempi di problemi NEXPTIME-completi

• Problemi succinti

• Logica

• Giochi

• Note

Un problema decisionale è mwfwNEXPTIME-completo se è in NEXPTIME, e ogni problema in NEXPTIME ha una mwgariduzione in tempo polinomiale ad esso. In altre parole, se esiste un mwgqalgoritmo in tempo polinomiale che trasforma le istanze di uno in istanze dell'altro con la stessa risposta. I problemi che sono NEXPTIME-completi potrebbero essere considerati i problemi più difficili in NEXPTIME. I problemi NEXPTIME-completi non sono in NP; è stato dimostrato che questi problemi non possono essere verificati in mwggtempo polinomiale, dal teorema della gerarchia temporale.

Un importante insieme di problemi mwhgNEXPTIME-completi riguarda mwhwi circuiti succinti. I circuiti succinti sono macchine semplici utilizzate per descrivere grafi in uno spazio esponenzialmente più piccolo. Accettano due indici di vertici come input e output, indipendentemente dalla presenza di un arco che li colleghi. Se risolvere un problema su un grafo in una rappresentazione naturale, come una mwiamatrice di adiacenza, è mwiqNP-completo, allora risolvere lo stesso problema su una rappresentazione circuitale succinta è mwigNEXPTIME-completo, perché l'input è esponenzialmente più piccolo (sotto una condizione in cui la riduzione della NP-completezza è ottenuta tramite una "proiezione").cite-ref-1[1] Come semplice esempio, trovare un mwjwcammino hamiltoniano per un grafo così codificato è mwkaNEXPTIME-completo.

Il problema della soddisfacibilità di una formula in logica del primo ordine con due variabili è NEXPTIME-completo.cite-ref-2[2] Il problema di soddisfacibilità della logica del primo ordine con conteggio e con due variabili è NEXPTIME-completo.cite-ref-3[3]

Decidere se una formula nelle formule booleana quantificate della dipendenza (DQBF, che è una versione con informazioni imperfette di mwnqQBF) è vera è NEXPTIME-completo.cite-ref-4[4]

cite-note-11. ↑ C. Papadimitriou. mwqaComputational Complexity Addison-Wesley, 1994. ISBNmwqg 0-201-53082-1. Section 20.1, pg.492.

cite-note-22. ↑ mwrg(mwrwmwsaEN) Etessami, mwsqmwsgFirst-Order Logic with Two Variables and Unary Temporal Logic, in mwswInformation and Computation, vol.mwta 179, 15 dicembre 2002, pp.mwtq 279–295, mwtgDOI:mwtw10.1006/inco.2001.2953, mwuaISSNmwuq 0890-5401.

cite-note-33. ↑ mwxaIan Pratt-Hartmann, mwxqProceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Association for Computing Machinery, 14 luglio 2014, pp.mwxg 1–10, mwxwDOI:mwya10.1145/2603088.2603117, mwyqISBNmwyg 978-1-4503-2886-9.

cite-note-44. ↑ mwzwGary L. Peterson e John H. Reif, mwaa20th Annual Symposium on Foundations of Computer Science (SFCS 1979), October 1979, pp.mwaq 348–363, mwagDOI:mwaw10.1109/SFCS.1979.25.